import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 970. 强整数
 * https://leetcode-cn.com/problems/powerful-integers/
 */
public class Solutions_970 {
    public static void main(String[] args) {
//        int x = 2, y = 3, bound = 10;  // output: {2, 3, 4, 5, 7, 9, 10}
        int x = 3, y = 5, bound = 15;  // output: {2, 4, 6, 8, 10, 14}

        List<Integer> result = powerfulIntegers(x, y, bound);
        System.out.println(result);
    }

    public static List<Integer> powerfulIntegers(int x, int y, int bound) {
        // 用 set 而不用 list，因为 x = 2, y = 3 时，会产生两个 5：2^2 + 3^0, 2^1 + 3^1
        Set<Integer> res = new HashSet<>();
        // 任何一位数的最小幂，是 1，所以遍历从 1 开始，直到 i 小于等于 bound
        for (int i = 1; i <= bound; ) {
            for (int j = 1; j + i <= bound; ) {
                // 范围为 [1, bound]
                res.add(i + j);
                if (y == 1) {
                    // 避免死循环，1 的任何次方都是 1
                    break;
                }
                // y = 3 时，能够组成 3^0 = 1, 3^1 = 3, 3^2 = 9, 3^3 = 27,...
                j = j * y;
            }
            if (x == 1) {
                break;
            }
            // x = 2 时，能够组成 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 8,...
            i = i * x;
        }
        return new ArrayList<>(res);
    }
}
